import java.util.HashSet;

/**
 * 136. 只出现一次的数字 https://leetcode.cn/problems/single-number/
 *学会使用异或运算
 */
public class SingleNumber {

    /**
     * 异或运算
     * 一个数和 0 做 XOR 运算等于本身：a⊕0 = a
     * 一个数和其本身做 XOR 运算等于 0：a⊕a = 0
     * XOR 运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
     * 也就是说多个数一起异或运算可以交换运算次序，那么运算结果肯定就是只有单个的那个数了
     */
    public static int singleNumber(int[] nums) {
        int ans = 0;
        for(int num: nums) {
            ans ^= num;
        }
        return ans;
    }

    public static int singleNumber2(int[] nums) {
        HashSet<Integer> numSet = new HashSet<>();
        for(int i = 0;i < nums.length;i++) {
            if(numSet.contains(nums[i])) {
                numSet.remove(nums[i]);
            } else {
                numSet.add(nums[i]);
            }
        }
        return numSet.iterator().next();
    }
}
